\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{作业七: 图论基本作业}


\author{夏知人 \\信息与计算科学   3210103669}

\begin{document}

\maketitle

\section{各数据结构间关系的理解}
邻接矩阵可以看做通过一个二维数组，来储存每两个顶点间边的权值。且通过顺序的互换，可以实现边上权的有向性。但是这种存储方式非常占用空间，因为其存储
的数组大小是顶点个数的平方。由于并不是所又顶点之间都必须要有边的连接，所以当顶点数目较多，但是顶点与顶点间边的数量不是很大时，这种使用二维数组的存储
方式会产生大量的数组空间冗余。这里就引入邻接表，使用一维数组储存顶点，但是将相邻的顶点通过链表的方式连接在每个顶点对应的数组后，在边较少时可以大大缩减存储空间。


\section{设计思路}
\subsection{邻接矩阵的设计}
构造一个二维数组和一个一维数组，其中二维数组用于存放两个顶点之间边的权，一维数组用于存放顶点的值。通过这种让边的权与顶点分离的方法，可以实现对顶点单独的输出和对
两个顶点间有向性的表述。


\subsection{邻接表的设计}
构造一个一维数组存放顶点，但是为每个顶点构建一个模板类，再构造一个邻接域的结构，让邻接域指向顶点，这样就实现了一个一维数组存放当前顶点和与其相连接的顶点的功能。


\subsection{存储方式选择的设计}
首先用户可以通过输入对应的数值来选择想要的存储方式，通过变量choice来控制对应存储方式的调用。当用户不想指定某种特定的存储方式时，可输入任意键跳过或输入回车由程序判断使用
哪种存储方式更加合适并执行该存储方式。判断的标准是当需要存储的顶点数量平方是边数量的10倍以上时，顶点数量较多而边数量较少，此时采用邻接表来存储数据；当需要存储的顶点数量
平方不到边数量的10倍时，顶点数量较少而边数量较多，此时采用邻接矩阵来存储数据。通过上述判断方法实现数据的高效存储。


\section{测试说明}
通过输入测试数据观察输出结果，可以发现，当输入的顶点数量平方是边数量的10倍以上时，采用的是邻接表来存储数据；当输入的顶点数量平方不到边数量的10倍时，采用的是
邻接矩阵来存储数据


\end{document}
